package 力扣日常刷题.木23一月.第03天303;

/**
 * @author 帅小伙
 * @date 2022/3/3
 * @description
 */
public class Demo33寻找两个有序数组的中位数 {


    /*
    * 1.一个数组求中位数  可以画一条分界线
    *
    * 2. 两个数组求中位数   画一个折线
    *       1. 左边的元素和右边的元素大致相等
    *       2. 红线左边的所有元素的数值  <= 红线右边的所有元素的数组
    *   那么中位数只与分割线两边的数字有关   左边最大值 右边最小值
    *
    * */


    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }

    }


    public int getKthElement(int[] num1, int[] num2, int k) {
        int length1 = num1.length, length2 = num2.length;
        int index1 = 0, index2 = 0;

        while (true) {
            //边界情况  第一个数组在分割线的
            if (index1 == length1) {
                return num2[index2 + k - 1];
            }
            if (index2 == length2) {
                return num1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(num1[index1], num2[index2]);
            }

            //正常情况    min 防止越界
            int half = k / 2;
            // 第一个分割线左边的元素
            int newIndex1 = Math.min(index1+half,length1) - 1;
            // 第二个分割线左边的元素
            int newIndex2 = Math.min(index2+half,length2) - 1;
            int pivot1 = num1[newIndex1],pivot2 = num2[newIndex2];
            if(pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            }else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }

    }

}
